﻿#define  _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>


//https://www.nowcoder.com/practice/eb94f6a5b2ba49c6ac72d40b5ce95f50?tpId=37&&tqId=21233&rp=1&ru=/ta/huawei&qru=/ta/huawei/question-ranking
// 统计字符个数
// 以计数排序的思路，时间复杂度为O(N)
//#include <stdio.h>
//#include <string.h>
//int main()
//{
//    int a[128] = { 0 };
//    memset(a, 0, sizeof(a));
//    int ch = 0;
//    while ((ch = getchar()) != '\n')
//    {
//        a[ch]++;
//    }
//    int k = 0;
//    for (int i = 0; i < 128; i++)
//    {
//        if (a[i] != 0)
//            k++;
//    }
//    printf("%d\n", k);
//    return 0;
//}


//https://leetcode.cn/problems/majority-element/
// 给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
// //就是这个数比其他所有数的总和多一个
//#include <stdlib.h>
//计数排序，有一个很大的测试案例不让你过
/*int majorityElement(int* nums, int numsSize) {
    int min = nums[0], max = nums[0];
    for (int i = 1; i < numsSize; i++)
    {
        if (nums[i] > max)
            max = nums[i];
        if (nums[i] < min)
            min = nums[i];
    }
    int range = max - min + 1;
    int* a = (int*)calloc(range, sizeof(int));
    for (int i = 0; i < numsSize; i++)
    {
        a[nums[i] - min]++;
    }
    int pos = 0;
    for (int i = 0; i < range; i++)
    {
        if (a[i] > numsSize / 2)
        {
            pos = i;
            break;
        }
    }
    free(a);
    return (pos + min);
}*/

//时间复杂度O(N)
//int majorityElement(int* nums, int numsSize) {
//    int m = 0, cnt = 0;
//    for (int i = 0; i < numsSize; ++i)
//    {
//        if (cnt == 0)
//            m = nums[i];
//        if (m == nums[i])
//            cnt++;
//        else
//            cnt--;
//    }
//    return m;
//}
//
//
//int main()
//{
//    int a[] = { 3,2,3 };
//    int sz = sizeof(a) / sizeof(a[0]);
//    int k = majorityElement(a, sz);
//    printf("%d\n", k);
//    return 0;
//}


//https://leetcode.cn/problems/middle-of-the-linked-list/
// 求链表的中间节点，快慢指针
//struct ListNode* middleNode(struct ListNode* head)
//{
//    struct ListNode* slow = head, * fast = head;
//    while (fast && fast->next)
//    {
//        slow = slow->next;
//        fast = fast->next->next;
//    }
//    return slow;
//}


//https://leetcode.cn/problems/reverse-linked-list/
// 反转链表
//struct ListNode* reverseList(struct ListNode* head)
//{
//    struct ListNode* newhead = NULL, * curr = head;
//    while (curr)
//    {
//        struct ListNode* next = curr->next;
//        curr->next = newhead;
//        newhead = curr;
//        curr = next;
//    }
//    return newhead;
//}

